#ifndef HUFFTREE_H
#define HUFFTREE_H

#include <map>
#include <iostream>
#include <vector>

using namespace std;

template <typename DType, typename Freq>
struct Tnode {
	Tnode* lChild;
	Freq freq;
	union {
		Tnode* rChild;
		DType data;
	};

	/* constructor of internal node */
	Tnode (Tnode* l, Tnode* r): 
		lChild(l),
		rChild(r), 
		freq((l->freq)+(r->freq)) 
	{}
	
	/* constructor of leaf node */
	Tnode (DType d, Freq f): 
		lChild(0), 
		data(d),
		freq(f) 
	{}
	
	~Tnode () {
		/* recursively delete the whole subtree */
		if (lChild){
			delete lChild;
			delete rChild;
		}
	}

	void getFreq();
	void print();
};

template<typename DType, typename Freq>
void Tnode<DType, Freq>::getFreq () {
	cout<<freq<<endl;
}

template<typename DType, typename Freq>
void Tnode<DType, Freq>::print() {
	if (lChild != 0) {
		cout<<"(internal node)"<<endl;
	} else {
		cout<<"["<<data<<"]"<<", "<<freq<<endl;
	}
}

typedef Tnode<char, int> tnode;

class Hufftree {
public:
	Hufftree (const map<char, int>&);
	void makecode(tnode*, int);
	void checkcode();
	void encode(const char*);
	void decode(const char*);

	inline tnode* getroot() {
		return root;
	}

private:
	tnode* root;
	map<char, vector<bool> > codebook;
};

#endif
